package com.success.toutiao;

import org.junit.Test;

/**
 * Desc: 2018.11.28
 * 头条面试，提供笔记本，编程3选1，第二题
 * leetcode：https://leetcode.com/problems/trapping-rain-water/
 * Create by John Jiang On 2018/12/19
 */
public class WaterProblem {

    public int trap(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }
        return helper(height, 0, height.length - 1);
    }

    public int helper(int[] height, int start, int end) {
        if (start + 1 == end) {
            return 0;
        }
        int index = start;
        int h = -1;
        for (int i = start + 1; i < end; i++) {
            if (height[i] > h) {
                index = i;
                h = height[i];
            }
        }
        if (h > 0  && (h > height[start] || h > height[end])) {
            int left = helper(height, start, index);
            int right = helper(height, index, end);
            return left + right;
        } else {
            h = Math.min(height[start], height[end]);
            int sum = 0;
            for (int i = start + 1; i < end; i++) {
                sum += (h - height[i]);
            }
            return sum;
        }
    }

    @Test
    public void test() {
        int[] input = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(input));
    }
}
